package 竞赛.周赛214;

import java.util.Arrays;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 第一题.java
 * @Description TODO
 * @createTime 2020年11月08日 10:29:00
 * 给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：
 *
 * nums[0] = 0
 * nums[1] = 1
 * 当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
 * 当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]
 * 返回生成数组 nums 中的 最大 值。
 */
public class 第一题 {
    public static void main(String[] args) {
        Solution solution=new Solution();
        int maximumGenerated = solution.getMaximumGenerated(3);
        System.out.println(maximumGenerated);
    }
    static class Solution {
        public int getMaximumGenerated(int n) {
            int[] res=new int[n+1];
            for(int i=0;i<res.length;i++){
                if(i==0){
                    res[0]=0;
                    continue;
                }
                if(i==1){
                    res[1]=1;
                    continue;
                }
              if(i%2==0){
                  res[i]=res[i/2];
              }else {
                    res[i]=res[i/2]+res[i/2+1];
              }
            }

            Arrays.sort(res);
            System.out.println(Arrays.toString(res));
            return res[res.length-1];
        }
    }

}
